import java.util.*;


public class Solution15 {
    public static void main(String[] args) {
        Solution15 solution = new Solution15();
        List<String> wordList = new ArrayList<>();
        wordList.add("hot");
        wordList.add("dot");
        wordList.add("dog");
        wordList.add("lot");
        wordList.add("log");
        wordList.add("cog");
        List<List<String>> ladders = solution.findLadders("hit", "cog", wordList);
    }
    // 使用广度优先搜索
    List<List<String>> result = new ArrayList<>();
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        if(!wordList.contains(endWord))return result;
        boolean flag = false;
        Deque<List<String>> deque = new LinkedList<>();
        Set<String> allSet = new HashSet<>();
        deque.add(new ArrayList<>(Arrays.asList(beginWord)));
        while(!deque.isEmpty() && !flag){
            Set<String> currentSet = new HashSet<>();
            for(int count = deque.size();count>0;count++){
                List<String> pollList = deque.poll();
                String poll = pollList.get(pollList.size() - 1);
                char[] pollChars = poll.toCharArray();
                for(int i =0;i<pollChars.length;i++){
                    char oldChar = pollChars[i];
                    for(int j ='a';j<'z';j++){
                        if((char)j == pollChars[i])continue;
                        pollChars[i] =(char)j;
                        String temp = new String(pollChars);
                        if(wordList.contains(temp) && !allSet.contains(temp)){
                            List<String> list = new ArrayList<>();
                            list.addAll(pollList);
                            list.add(temp);
                            if(temp.equals(endWord)){
                                flag = true;
                                result.add(list);
                            }
                            deque.add(list);
                            currentSet.add(temp);
                        }
                    }
                    pollChars[i]=oldChar;
                }
            }
            allSet.addAll(currentSet);
        }
        return result;
    }

}
